package 算法.LeetCode91.每日打卡题目;

import java.util.Arrays;
import java.util.HashSet;

/**
 * @author:谢君臣
 * @Date:2021/3/1821:08
 * @version:1.0
 * @function: 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 * 示例 1：
 * 输入：s = "ADOBECODEBANC", t = "ABC"
 * 输出："BANC"
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-window-substring
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day38 {
    public static void main(String[] args) {
        System.out.println(minWindow("b",
                "b"));
    }

    public static String minWindow(String s, String t) {
        String res = null;
        if (t.length()>s.length())
            return "";
        int[] c1 = new int[26 * 2];
        int[] c2 = new int[26 * 2];
        int[] c3 = new int[26 * 2];
        HashSet<Character> hashSet = new HashSet<>();
        for (int i = 0; i < t.length(); i++) {
            hashSet.add(t.charAt(i)); // 记录目标串中字符
            int index = t.charAt(i) - 'a' >= 0 ? t.charAt(i) - 'a' : t.charAt(i) - 'a' + 58;
            c1[index]++;
        }
        boolean flag = false;
        for (int l = 0, r = 0; r < s.length(); r++) {
            if (hashSet.contains(s.charAt(r))) {
                flag = true;
                int index = s.charAt(r) - 'a' >= 0 ? s.charAt(r) - 'a' : s.charAt(r) - 'a' + 58;
                int temp1 = c1[index];      // 目标结果
                int temp2 = c3[index] + 1;   // 当前结果
                c2[index] = Math.min(temp2 , temp1);
                c3[index] = temp2;
            }
            if (!flag)
                l++;
            while (Arrays.equals(c1, c2)) {
                String temp = s.substring(l, r+1);
                if (res == null)
                    res = temp;
                else
                    res = res.length() < temp.length() ? res : temp;
                int index = s.charAt(l) - 'a' >= 0 ? s.charAt(l) - 'a' : s.charAt(l) - 'a' + 58;
                // 统计被剔除的元素个数是否大于目标值

                c2[index] = c3[index]>c1[index]?c1[index]:c1[index]-1; // 将当前已匹配的删掉
                c3[index]--;
                l++;      // 左指针进一位
                while (l<r&&!hashSet.contains(s.charAt(l)))  // 判断后面l-r 中间是不是目标字符
                    l++;
            }
        }
        return res==null?"":res;
    }
}
